A prefix search is used in networking to route and classify packets. The route to be used for a packet and its classification are determined by finding the longest matching prefix in a set. For example a packet using IPv6 (internet protocol version 6) has a 128-bit destination address. A router determines the output port over which such a packet should be routed by searching a set of variable-length binary strings to find the longest string that matches a prefix of the destination address. For classification purposes, other fields of the header, such as the port number, may also be included in the string to be matched.
To illustrate the problem of prefix search, consider the list of prefix character strings shown in FIG. 1 in alphabetical order. The principle is the same with binary strings. Given a search string, such as xe2x80x9ccaceaxe2x80x9d, the goal is to find the longest stored string that exactly matches a prefix of this string. Although a simple linear search of the list finds that this string falls between xe2x80x9ccabxe2x80x9d and xe2x80x9ccadxe2x80x9d, one must scan several strings backward from this point to find that the longest matching prefix is xe2x80x9ccaxe2x80x9d In actual routing tables, which may contain hundreds of thousands of entries, the matching prefix may be far from the point where the linear search fails. An optimized data structure is needed to efficiently find the matching prefix.
A prior method for performing longest prefix matching employs a data structure called a trie. A trie for the prefix list of FIG. 1 is shown in FIG. 2. As shown, the trie is a tree structure in which each node of the tree resolves one character of the string being matched. Each internal node consists of a list of characters. Associated with each character is an outgoing link either to another internal node, a rectangle in the figure, or to a leaf node, a circle in the figure. A slash at the start of a node indicates that a prefix leading to that node with no additional characters is part of the list. Each leaf node holds the result data associated with the prefix leading to that leaf node, and in the figure, the leaf nodes are labeled with these prefixes. The result data might, for example, be the output port associated with a data packet and a flow-identifier.
To search the trie, one starts at the root node, node 1 in the figure, and traverses the tree by following the outgoing link at each node conesponding, to the next character in the string to be matched. When no matching outgoing link can be found, the longest matching prefix has been found. For example, given the string xe2x80x9ccaceaxe2x80x9d we start at node 51. The xe2x80x9ccxe2x80x9d directs us to node 54. The xe2x80x9caxe2x80x9d directs us to node 58. As we cannot find a match for the next character, xe2x80x9ccxe2x80x9d, at node 58, we follow the link associated with the slash to the leaf node associated with the longest matching prefix, xe2x80x9ccaxe2x80x9d. Note that if prefix xe2x80x9ccaxe2x80x9d were not in the list, we would need to backtrack at this point to node 54 for prefix xe2x80x9ccxe2x80x9d.
Another prior method for prefix matching is to perform binary search on a table. However, as described by Radial Perlman, Interconnections, Bridges and Routers, Addison Wesley, 1992, pages 233-239, and shown in FIG. 3, since binary search will find the closest matching string, rather than the longest matching prefix, we must make two modifications to the list to apply this technique. First, we insert two entries for every entry in the list that encloses other entries, that is, that would serve as a longest matching prefix for another prefix in the list but for the other prefix itself being in the list. One of those entries is terminated by the symbol 0, which comes alphabetically before all characters, and one by the symbol 1, which comes alphabetically after all characters. These two entries act as parentheses enclosing all entries that contain the prefix. Second, we attach to each entry in the list not ending in a 0 a pointer to the nearest enclosing entry. FIG. 3 shows the list of FIG. 1 augmented in this manner. Note that the prefix xe2x80x9ccaxe2x80x9d has been replaced by the two entries xe2x80x9cca0xe2x80x9d and xe2x80x9cca1xe2x80x9d that bracket all entries containing the prefix xe2x80x9ccaxe2x80x9d and that all of these entries have a pointer back to xe2x80x9cca0xe2x80x9d.
To search the augmented list of FIG. 3 for the longest matching prefix, one searches for a string equal to a prefix of the target or the alphabetically closest pair of strings. Strings ending in xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d never exactly match a prefix of the target string because xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d do not match any character of the target string. If the search finds an exact prefix of the target string, the result data associated with the string is retrieved. Otherwise, the search found the closest pair of stored strings, Sa and Sb. in this case there are three possibilities:
1. If Sa ends in a xe2x80x9c0xe2x80x9d symbol, then the longest matching prefix is this string with the xe2x80x9c0xe2x80x9d removed.
2. If Sb ends in a xe2x80x9c1xe2x80x9d symbol, then the longest matching prefix is this string with the xe2x80x9c1xe2x80x9d removed.
3. Otherwise, an enclosing pointer from Sa is followed to find a string ending in a xe2x80x9c0xe2x80x9d symbol which encloses Sa and the nearest match is that string with the xe2x80x9c0xe2x80x9d symbol removed.
For example, a search for xe2x80x9ccaceaxe2x80x9d will end between xe2x80x9ccabxe2x80x9d and xe2x80x9ccadxe2x80x9d. Since this is not an exact match, xe2x80x9ccabxe2x80x9d does not end in xe2x80x9c0xe2x80x9d, and xe2x80x9ccadxe2x80x9d does not end in xe2x80x9c1xe2x80x9d, the pointer from xe2x80x9ccabxe2x80x9d is followed back to xe2x80x9cca0xe2x80x9d giving the longest matching prefix, xe2x80x9ccaxe2x80x9d. Similarly a search for xe2x80x9ccbxe2x80x9d will end between xe2x80x9cca1xe2x80x9d and xe2x80x9cccxe2x80x9d and follow the pointer from xe2x80x9cca1xe2x80x9d back to the common prefix, xe2x80x9ccxe2x80x9d.
While the trie structure and binary search strategy work, they are not well suited for implementation in a hardware search engine. The trie requires a memory access for every character of a string and possible backtracking if a match is not found. This makes it inefficient in terms of memory bandwidth usage. The binary search strategy requires storing two result pointers for the majority of prefixes, one for a direct match and one to the enclosing string or its associated result. This makes it inefficient in terms of memory usage.
The prior application Ser. No. 09/104,314, filed Jun. 25, 1998 discloses and claims a data structure, an augmented tree, that stores prefix sets in a manner that enables efficient searching and a hardware engine for searching the augmented tree. The augmented tree stores the prefix set with enclosing prefixes in a tree structure similar to a B-tree, a tree with a radix greater than one previously used to efficiently search for exact matches by optimizing the tree node size to the size of data blocks retrieved from storage discs. The prefix search data structure comprises a tree structure having internal nodes for identifying subsequent nodes from prefix search keys. Leaf nodes each comprise a set of prefix keys to be compared to a prefix search key. The sets of prefix keys of plural leaf nodes together form a list of prefix keys including enclosing prefix key pairs.
In accordance with the present invention, prefix search circuitry is provided on an integrated circuit. A plurality of prefix search engines are provided oil the integrated circuit, each engine performing a prefix search of a prefix search data structure based on a prefix search key.
Preferably, prefix search keys embedded in input packet descriptors are distributed from an input queue over an internal network to the plural search engines and the results of the prefix searches are forwarded to an output queue. At the output queue, the search results are ordered in the same order that the corresponding input packet descriptors arrived at the input queue. The internal network may include an input bus from the input queue to the search engines and an output bus from the engines to the output queue.
Preferably, the search engines on the integrated circuit are associated with an array of memory units, each unit dedicated to a search engine within the integrated circuit. Each search engine reads data in bursts over integrated circuit data pins dedicated to the search engine, and each search engine addresses a memory unit over integrated circuit pins shared with another search engine. Preferably, each memory unit is a synchronous dynamic random access memory (SDRAM) which comprises plural banks of memory cells, and a prefix search tree data structure is stored across the plural banks to provide access to the tree structure in successive read cycles. Internal nodes of the tree structure arc duplicated across plural banks, and leaf nodes are interleaved across plural banks.
The preferred prefix search engine comprises a data register which receives data of a tree structure from memory, a search key register, a comparator and an address calculator. The comparer compares a search key in the search key register with data from the data register, and the address calculator calculates memory addresses based on the comparator output to read the data from memory into the data register.